package io.tec.cloud.algorithm.c05_v20220617;


import io.tec.cloud.algorithm.AlgorithmUtil;

import java.util.Arrays;

/**
 * 35	快速排序1.0
 * 每次只确认一个位置
 */
public class T35_QuickSort1_0 {

    public static void quickSort1_0(int[] arr) {

        if (arr == null || arr.length < 2) {
            return;
        }

        process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int l, int r) {

        // base case
        if (l >= r) {
            return;
        }

        int equals = partition(arr, l, r);

        process(arr, l, equals - 1);
        process(arr, equals + 1, r);
    }

    // 两种划分方式：
    // 方法1：arr[L...R]，以arr[R]为划分值，<=arr[R]放在左边，>arr[R]在右边，影响变量名称及判断条件：arr[idx] <= arr[r]
    // 方法2：arr[L...R]，以arr[R]为划分值，<arr[R]放在左边，>=arr[R]在右边，影响变量名称及判断条件：arr[idx] < arr[r]
    private static int partition(int[] arr, int l, int r) {

        if (l > r) {
            return -1;
        }

        if (l == r) {
            return l;
        }

        int li = l - 1;
        // TODO 从l开始
        int idx = l;
        while (idx < r) {
            // <
            if (arr[idx] < arr[r]) {
                AlgorithmUtil.swap(arr, ++li, idx);
            }
            idx++;
        }
        AlgorithmUtil.swap(arr, r, ++li);
        return li;
    }

    public static void main(String[] args) {
        int testTimes = 100_0000;
        int maxValue = 100;
        int maxLength = 100;
        for (int t = 0; t < testTimes; t++) {
            int[] arr = AlgorithmUtil.generateArray(maxValue, AlgorithmUtil.randomWithoutTarget(maxLength));
            int[] arr1 = AlgorithmUtil.copyArray(arr);
            int[] arr2 = AlgorithmUtil.copyArray(arr);
            quickSort1_0(arr1);
            Arrays.sort(arr2);
            if (!AlgorithmUtil.isEquals(arr1, arr2)) {
                AlgorithmUtil.printArray(arr);
                AlgorithmUtil.printArray(arr1);
                AlgorithmUtil.printArray(arr2);
                System.out.println("error");
                break;
            }
        }
        System.out.println("finish");
    }
}

